Knowing network capacity is useful for many network applications to improve their performance. Network capacity (or bottleneck bandwidth) refers to the smallest transmission rate of a set of network links, forming a network path from a source to a destination. Existing tools for capacity measurement are mostly based on active methods: they inject probe packets to the network path under measurement. Capacity measurement is a challenging task in practice, because the accuracy and speed can be adversely affected by cross traffic present on the path. The cross traffic is the network traffic other than the traffic introduced by a capacity measurement method. Moreover, it is preferred to minimize the amount of overheads, which includes the amount of traffic introduced for capacity measurement, and the storage and computation requirement at the measuring node.
Existing capacity measurement tools are based on two main approaches: variable packet size (VPS) and packet dispersion. The VPS-based methods, such as clink, pathchar, and pchar, measure the capacity for each hop of the path with different packet sizes. As a result, a large number of measurements are conducted for each hop and for the entire path, thus requiring a long time for obtaining a capacity estimate and introducing a significant amount of measurement traffic to the network path.
The packet dispersion approach, on the other hand, makes use of the dispersion of two or more probe packets to measure the capacity of an end-to-end path. In particular, the packet-pair dispersion (PPD) technique, which has been used by many tools, such as Bprobe, SProbe, Capprobe, and AsymProbe, sends a pair of back-to-back probe packets to measure the dispersion of the two packets at the bottleneck link. The network capacity is then given by the probe packet size divided by the dispersion.
The accuracy and speed of the PPD technique, however, could be seriously degraded by the cross traffic present on the path under measurement. Therefore, the basic PPD technique is usually augmented by a cross-traffic filtering technique to filter measurement samples that may have been biased by cross traffic. For example, Bprobe proposed in R. Carter and M. Crovella, “Measuring Bottleneck Link Speed in Packet-Switched Networks,” Performance Evaluation, 1996 filters inaccurate estimates using union and intersection of packet-pair measurements with different packet sizes. SProbe proposed in S. Saroiu, P. Gummadi, and S. Gribble, “SProbe: A Fast Technique for Measuring Bottleneck Bandwidth in Uncooperative Environments,” Proc. IEEE INFOCOM, 2002 uses two heuristics to discard samples that have abnormally small dispersion and packet reordering.
Kapoor et al., “CapProbe: A Simple and Accurate Capacity Estimation Technique,” Proc. ACM SIGCOMM, 2004 proposes the use of a minimum delay sum (MDSUM) method to filter out measurements that do not meet a minimum delay sum condition. The MDSUM method is used in both CapProbe and AsymProbe to filter inaccurate measurement samples. Pasztor and Veitch, “The Packet Size Dependence of Packet-pair Like Methods,” Proc. IWQoS, 2002 analyzes several types of components embedded in the dispersion and selects the capacity mode from a high-resolution histogram.
However, the existing cross-traffic filtering techniques still suffer from slow speed and inefficiencies. Applications, such as determining optimal software download rates, forming peer-to-peer networks, and establishing multicast trees, will benefit from a fast estimation of network capacity. Moreover, injecting a large amount of probe traffic unnecessarily not only prolongs the estimation process, but also affects the normal traffic and introduces additional processing burdens to both the measuring and remote nodes.
The Bprobe measurement can be very slow, because it requires several phases with different probe sizes before arriving at the capacity estimation. It introduces a large number of varied-sized probes packets to the network path and requires the measuring node to retain the distribution of the bandwidth estimates for each phase for the intersection and union filtering. The memory requirement therefore increases with the bin size and the number of phases.
The SProbe's two filtering heuristics are very limited in practical applications. It does not consider the dispersion samples that may be over-estimated or under-estimated due to the presence of cross traffic. Previous studies have shown that the dispersion could be distorted by two types of cross traffic. The first type is the traffic already existing in a forwarding node located after the bottleneck link when the first probe/response packet arrives. This cross traffic could delay the first packet to the extent that the dispersion is compressed, causing a capacity overestimation. The second type is the traffic intervening the first and second probe/response packets in a forwarding node. This cross traffic could increase the second packet's queueing delay, thus causing a capacity underestimation.
The MDSUM filtering method filters out the dispersion samples that do not meet a minimum delay sum condition. The basic idea is that if any packet in a packet pair is interfered by cross traffic, additional packet delay will be introduced; therefore, a sum of the two packets' delay (i.e., a delay sum) will also increase. The drawback of the MDSUM technique is that it considers only the packet pair whose packets are both unaffected by cross traffic. It therefore discards all other packet pairs, including those in which only a single packet has been interfered. As a result, useful information in those packet pairs is not fully utilized to speed up the measurement process.
In Pasztor and Veitch, “The Packet Size Dependence of Packet-pair Like Methods,” Proc. IWQoS, 2002, the measurement accuracy depends on the maximum resolution that can be supported by the measuring node. Using smaller bins would require a higher number of probe pairs, thus resulting in increasing either the average probing rate (thus the intrusiveness to the network) or time for obtaining the capacity estimate. Moreover, as the bin width decreases, more memory space will be required for the measurement.
Besides the PPD method, the packet train dispersion (PTD) technique is another example of the packet dispersion approach. The PTD technique performs capacity measurement based on the dispersion of a burst of back-to-back probe packets. Pathrate proposed in C. Dovrolis, P. Ramanathan, and D. Moore, “Packet Dispersion Techniques and a Capacity-Estimation Methodology,” IEEE/ACM Trans. Networking, vol. 12, no. 6, 2004 uses both PPD and PTD for capacity measurement. DSLprobe proposed in D. Croce et al., “Capacity Estimation of ADSL Links,” Proc. ACM CoNEXT, 2008 exploits the PTD technique for capacity measurement and various methods to remove any cross-traffic interfered spacing between adjacent packets in the packet train. Besides introducing a significant amount of probe traffic, another notable problem with the PTD technique is that as the trunk length increases, it is more likely for the packet train to be affected by cross traffic.
As a result, the need remains for a reliable method for capacity measurement of an end-to-end path which obtains the capacity estimate rapidly and efficiently.